Paper 2015/377

Cluster Computing in Zero Knowledge

Alessandro Chiesa, Eran Tromer, and Madars Virza

Abstract

Large computations, when amenable to distributed parallel execution, are often executed on computer clusters, for scalability and cost reasons. Such computations are used in many applications, including, to name but a few, machine learning, webgraph mining, and statistical machine translation. Oftentimes, though, the input data is private and only the result of the computation can be published. Zero-knowledge proofs would allow, in such settings, to verify correctness of the output without leaking (additional) information about the input. In this work, we investigate theoretical and practical aspects of *zero-knowledge proofs for cluster computations*. We design, build, and evaluate zero-knowledge proof systems for which: (i) a proof attests to the correct execution of a cluster computation; and (ii) generating the proof is itself a cluster computation that is similar in structure and complexity to the original one. Concretely, we focus on MapReduce, an elegant and popular form of cluster computing. Previous zero-knowledge proof systems can in principle prove a MapReduce computation's correctness, via a monolithic NP statement that reasons about all mappers, all reducers, and shuffling. However, it is not clear how to generate the proof for such monolithic statements via parallel execution by a distributed system. Our work demonstrates, by theory and implementation, that proof generation can be similar in structure and complexity to the original cluster computation. Our main technique is a bootstrapping theorem for succinct non-interactive arguments of knowledge (SNARKs) that shows how, via recursive proof composition and Proof-Carrying Data, it is possible to transform any SNARK into a *distributed SNARK for MapReduce* which proves, piecewise and in a distributed way, the correctness of every step in the original MapReduce computation as well as their global consistency.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2015
Keywords
zero knowledgecluster computingMapReduceproof-carrying datasuccinct arguments
Contact author(s)
alexch @ berkeley edu
History
2015-04-28: revised
2015-04-27: received
See all versions
Short URL
https://ia.cr/2015/377
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/377,
      author = {Alessandro Chiesa and Eran Tromer and Madars Virza},
      title = {Cluster Computing in Zero Knowledge},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/377},
      year = {2015},
      url = {https://eprint.iacr.org/2015/377}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.